class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
        for i in range(len(s)):
            for j in range(i, len(s) + 1):
                print(s[i:j])
                if i == j:  # 单个字符
                    dp[i][j] = 1
                    continue
                if i == j - 2 and s[i] == s[j - 1]:  # 两个字符
                    dp[i][j] = 1
                    continue
                if (dp[i + 1][j - 1] == 1 and s[i] == s[j - 1]):
                    dp[i][j] =  1
                else:
                    dp[i][j-1] = 0
                
        return 0

if __name__ == '__main__':
    s = Solution()
    print(s.longestPalindromeSubseq("bbbab"))